package com.le.tester.imooc.oldfairy.coding.datastructure;

import org.junit.Test;

import java.util.Queue;

/**
 * createTime：2023/5/26 15:55
 * description：二叉搜索树
 */
public class BSTree<T extends Comparable> {

    BSNode<T> root = null;

    static class BSNode<T> {

        BSNode<T> left = null;
        BSNode<T> right = null;

        T data;

        public BSNode(T data) {
            this.data = data;
        }
    }


    private void add(BSNode<T> node, BSNode<T> element) {

        if (element.data.compareTo(node.data) <= 0) {
            if (element.left == null) {
                node.left = element;
                return;
            }

            add(node.left, element);
        } else {
            if (element.right == null) {
                node.right = element;
                return;
            }
            add(node.right, element);
        }
    }

    public void add(T element) {

        BSNode<T> node = new BSNode<>(element);

        if (root == null) {
            root = node;
            return;
        }

        add(root, node);
    }

    //树的翻转
    public static <T> void reverse(BSNode<T> node) {
        if (node == null) {
            return;
        }
        BSNode<T> left = node.left;
        node.left = node.right;
        node.right = left;

        reverse(node.left);
        reverse(node.right);

    }

    //广度优先遍历
    public static <T> void bfs(BSNode<T> node) {
        //使用双向队列先进先出的特性
        LQueue<BSNode<T>> tlQueue = new LQueue<>();
        tlQueue.enQueue(node);

        while (tlQueue.size() > 0) {
            BSNode<T> tbsNode = tlQueue.deQueue();
            System.out.println(tbsNode.data);

            if (tbsNode.left != null)
                tlQueue.enQueue(tbsNode.left);

            if (tbsNode.right != null)
                tlQueue.enQueue(tbsNode.right);

        }


    }


    @Test
    public void testBSTree() {
        BSTree<Integer> bsTree = new BSTree<>();
//        for (int i = 0; i < 50; i++) {
//            bsTree.add((int) (Math.random() * i));
//        }
        bsTree.add(10);
        bsTree.add(7);
        bsTree.add(5);
        bsTree.add(8);
        bsTree.add(15);
        bsTree.add(30);
        bsTree.add(21);
        TreePrinter treePrinter = new TreePrinter();
        treePrinter.print(bsTree.root);


    }
}
